package Z.dailyExercise.holiday;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class _剑指Offer68II二叉树的最近公共祖先 {
    /**
     * 不同于另一个公共祖先 这个是二叉树 没有大小规律 所以不能采取比大小方式
     * ===存父节点的方式
     * @param root
     * @param p
     * @param q
     * @return
     */
    public Map<TreeNode,TreeNode> map = new HashMap<>();
    public Set<TreeNode> set = new HashSet<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        getparent(root);

        while (p != null){
            set.add(p);
            p = map.get(p);

        }

        while (q != null){
            if (set.contains(q)){
                return q;
            }
            q = map.get(q);
        }
        return null;

    }

    public void getparent(TreeNode root){
         if (root.left != null){
             map.put(root.left,root);
             getparent(root.left);

         }

         if (root.right != null){
             map.put(root.right,root);
             getparent(root.right);
         }
    }

    /**
     * 另解：如果当前root是所求公共解的话  p和q肯定是在其两侧 或者本身就是p或者q
     * 所以可以采取后续遍历 遇到p｜q时返回
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null){
            return null;
        }

        if (root == p || root ==q){
            return root;
        }

        TreeNode left= lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        //上面两个节点 要么是空 要么就是p｜q
        if (left == null){
            return right;//因为总要有个返回值 所以不管这个right是不是空了 交给上一层的进行判断好了
        }else if (right == null){
            return left;
        }else {
            return root;
        }

    }
}
